package com.klun.tree.binaryTree;

import org.apache.commons.lang.StringUtils;
import sun.swing.StringUIClientPropertyKey;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 分别用递归和非递归方式实现二叉树先序、中序和后序遍历
 */
public class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int value) {
        this.value = value;
    }
	public Node() {}

	/**
	 * 测试方法
	 * @param args
	 */
	public static void main(String[] args) {
		/*创建一个二叉树*/
		Node root = new Node(1);
		root.left = new Node(2);
		root.left.left = new Node(3);
		root.left.right = new Node(4);
		root.left.left.left = new Node(5);
		root.right = new Node(6);
		root.right.left = new Node(7);
		root.right.right = new Node(8);
		/**
		 					1
		 				  /   \
						2		6
		 			   /  \    /  \
		 			 3	   4  7		8
		 			/
		 		  5
		 */
		/*先序遍历*/
		preOrderRecur(root);
		System.out.println();
		/*中序遍历*/
		inOrderRecur(root);
		System.out.println();
		/*后序遍历*/
		posOrderRecur(root);
		System.out.println();

//		/*遍历交换位置*/
		preOrderAndChange(root);
//		/*先序遍历 新树*/
		preOrderRecur(root);

//		/*序列化*/
//		System.out.println(serialByPre(root));
//		/*反序列化*/
//		preOrderRecur(reconByPreString(serialByPre(root)));
//		System.out.println();
	}

	/**
	 * 二叉树的序列化
	 * @param head
	 * @return
	 */
	public static String serialByPre(Node head){
		if(head == null){
			return "#!"; // 叶节点
		}
		String res = head.value + "!";
		res += serialByPre(head.left);
		res += serialByPre((head.right));
		return res;
	}

	/**
	 * 二叉树的反序列化
	 * @param preStr
	 * @return
	 */
	public static Node reconByPreString(String preStr){
		String[] values = preStr.split("!");
		Queue<String> queue = new LinkedList<String>();
		for (String a:queue) {
			queue.offer(a);
		}
		return reconPreOrder(queue);
	}
	public static Node reconPreOrder(Queue<String> queue){
		String value = queue.poll();
		if(StringUtils.isNotEmpty(value) && value.equals("#")){
			return null;
		}
		Node head = new Node(Integer.valueOf(value));
		head.left = reconPreOrder(queue);
		head.right = reconPreOrder(queue);
		return head;
	}

	/**
	 * 先序遍历+交换位置
	 * @param head
	 */
	public static void preOrderAndChange(Node head){

		/*如果此节点为空返回上一层*/
		if(head == null){
			return;
		}
		/*交换位置*/
		Node left = null;
		Node right = null;
		if(null != head.left){
			left = head.left;
		}
		if(null != head.right){
			right = head.right;
		}
		head.left = right;
		head.right = left;

		/*递归调用*/
		preOrderAndChange(head.left);
		preOrderAndChange(head.right);
	}



	/**
     * 先序遍历 - 递归
     * @param head
     */
    public static void preOrderRecur(Node head){
        if(head == null){
            return;
        }
        System.out.print(head.value+"-");
        // 先遍历左侧的元素 打印出来 依次遍历右侧的元素(根据去时的元素)
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    /**
     * 递归 - 中序遍历
     * @param head
     */
    public static void inOrderRecur(Node head){
        if(head == null){
            return;
        }

        inOrderRecur(head.left);
        System.out.print(head.value+"-");
        inOrderRecur(head.right);
    }
    /**
     * 递归 - 后序遍历
     * @param head
     */
    public static void posOrderRecur(Node head){
        if(head == null){
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.value+"-");
    }

    /**
     * 非递归 - 先序排序
     * @param head
     */
    public void preOrderUnRecur(Node head){
        System.out.println("pre-order: ");
        if( head != null){
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while(!stack.isEmpty()){
                head = stack.pop();
                System.out.println(head.value+" ");
                if (head.right != null){
                    stack.push(head.right);
                }
                if (head.left != null){
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

}
